package com.xieyong.leetcode;

import java.util.Arrays;

public class Leetcode1751 {

    public static void main(String[] args) {
        Leetcode1751 leetcode1751 = new Leetcode1751();
        int[][] events = {{21,77,43},{2,74,47},{6,59,22},{47,47,38},{13,74,57},{27,55,27},{8,15,8}};
//        int[][] events = {{87,95,42},{3,42,37},{20,42,100},{53,84,80},{10,88,38},{25,80,57},{18,38,33}};
        int k = 4;
        int i = leetcode1751.maxValue(events, k);
        System.out.println(i);
    }



    public int maxValue(int[][] events, int k) {
        if (k == 1) {
            int mx = 0;
            for (int[] e : events) {
                mx = Math.max(mx, e[2]);
            }
            return mx;
        }
        Arrays.sort(events,(a,b)->a[1]-b[1]);
        int n = events.length;
        int[][] dp = new int[n + 1][k + 1];
//        Arrays.fill(dp[0], 0);
//        for (int i = 0; i < n; i++) {
//            dp[i][0] = 0;
//        }

//        for (int i = 0; i < n; i++) {
        for (int i = 1; i <= n; i++) {
            int start = events[i - 1][0];
            int end = events[i - 1][1];
            int value = events[i - 1][2];

            int last = 0;
            for (int j = i - 1;j >= 1;j--) {
                if (events[j - 1][1] < start) {
                    last = j;
                    break;
                }
            }
            for (int j = 1; j <= k; j++) {
                dp[i][j] = Math.max(dp[last][j - 1] + value, dp[i - 1][j]);
            }
//            for (int j = 1; j <= k; j++) {
//                int p = findp(events,events[i][0]);
//                dp[i + 1][j] = Math.max(dp[p][j - 1] + events[i][2], dp[i][j]);
//            }
        }
//        for (int i : dp[0]) {
//            System.out.print(i + " ");
//        }
//        for (int i = 1; i < dp.length; i++) {
//            System.out.println();
//            int[] ints = dp[i];
//            System.out.print(events[i - 1][0] + "--" + events[i - 1][1] + "--" + events[i - 1][2] + ": ");
//            for (int anInt : ints) {
//                System.out.print(anInt + " ");
//            }
//        }
        return dp[n][k];
    }

//    private int findp(int[][] events, int target) {
//        int left = 0, right = events.length;
//        while (left < right) {
//            int mid = (right + left) / 2;
//            if (events[mid][1] < target) {
//                left = mid + 1;
//            } else {
//                right = mid;
//            }
//        }
//        return left;
//    }
}
